package top.minuy.structure.tree.trie;

import top.minuy.structure.map.BSTMap;

/**
 * 字典树
 *
 * @author Minuy
 * @time 19:34
 * @date 2021/10/5
 */
public class Trie {
    // 节点
    class Node{
        // 是不是单词末尾
        boolean isWord;
        // 子节点
        BSTMap<Character, Node> next;

        public Node(boolean isWord){
            this.isWord = isWord;
            next = new BSTMap<>();
        }

        public Node(){
           this(false);
        }
    }

    private Node root;
    private int size;

    public Trie(){
        size = 0;
        root = new Node();
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    public void add(String str){
        Node cur = root;
        for (int i=0;i<str.length();i++){
            char c = str.charAt(i);
            if (cur.next.get(c) == null){
                cur.next.add(c,new Node());
            }
            // 这里不能把cur.next.get(c)的值缓存起来，因为为空时会新建，这里只能获取最新值
            cur = cur.next.get(c);
        }
        if(!cur.isWord) {
            cur.isWord = true;
            size++;
        }
    }

    /**
     * 查询字符串是否存在Trie树中
     * @param str 要查询的字符串
     * @return 是否存在字典树中
     */
    public boolean contains(String str){
        Node cur = root, temp;
        for (int i=0;i<str.length();i++){
            char c = str.charAt(i);
            // 这边没有涉及修改操作，可以使用缓存
            temp = cur.next.get(c);
            if (temp == null){
                return false;
            }
            // 要更改游标
            cur = temp;
        }
        return cur.isWord;
    }

    /**
     * 是否存在某个前缀
     * @param prefix 前缀
     * @return 是否存在
     */
    public boolean isPrefix(String prefix){
        Node cur = root,temp;
        for (int i=0;i<prefix.length();i++){
            temp = cur.next.get(prefix.charAt(i));
            if(temp==null){
                return false;
            }
            cur = temp;
        }
        return true;
    }
}
